#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_set>
using namespace std;


struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x):val(x), next(nullptr){}
};

class Solution{
    public:
    bool ans1(ListNode* head){
        unordered_set<ListNode*> seen;
        while (head != nullptr) {
            if (seen.count(head)) {
                return true;
            }
            seen.insert(head);
            head = head->next;
        }
        return false;
    }

    bool ans2(ListNode* head){
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (slow != fast) {
            if (fast == nullptr || fast->next == nullptr) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }
};

void test1(){
    ListNode* head = NULL;
    ListNode* head1 = new ListNode(3);
    ListNode* head2 = new ListNode(2);
    ListNode* head3 = new ListNode(0);
    ListNode* head4 = new ListNode(-4);

    head = head1;
    head1->next = head2;
    head2->next = head3;
    head3->next = head4;
    head4->next = head1;
    
    Solution s;
    // bool ret = s.ans1(head);
    bool ret = s.ans2(head);
    cout << ret << endl;
}

void test2(){
    ListNode* head = NULL;
    ListNode* head1 = new ListNode(1);
    ListNode* head2 = new ListNode(2);

    head = head1;
    head1->next = head2;
    head2->next = head1;

    Solution s;
    // bool ret = s.ans1(head);
    bool ret = s.ans2(head);
    cout << ret << endl;
}

void test3(){
    ListNode* head = NULL;
    ListNode* head1 = new ListNode(1);

    head = head1;

    Solution s;
    // bool ret = s.ans1(head);
    bool ret = s.ans2(head);
    cout << ret << endl;
}

int main(void){
    test1();
    test2();
    test3();

    return 0;
}